Corelab Seminar
2009-2010
George Pierrakos (UC Berkeley, NTUA)
"Learning" Equilibria in Games.
Abstract . Can learning algorithms find a Nash equilibrium? This is an interesting question for many reasons; learning algorithms are arguably a very natural class of algorithms that resemble the behavior of players in many practically arising game settings. Another reason to consider this question is in the hope of being able to prove an impossibility result, not dependent on complexity assumptions, for computing Nash equilibria via a restricted class of (reasonable) algorithms.
We will review the basic ideas behind the multiplicative weights update method (the "experts" framework) and show how it can be used to solve zero-sum games approximately. We will then discuss how the same class of algorithms impressively fails to find the unique equilibrium in a very simple game defined by Shapley in the 50s; this game was used to establish that fictitious play (another type of learning algorithm that does not fall into the standard experts framework) does not converge in general games (note however that fictitious play does converge for zero-sum games and for some other special types of games).